"""
最长公共子序列
求序列X（长m） 与序列Y（长n）的最长公共子序列
c[i][j]存放长度
b[i][j]标记，用于求解
"""

import numpy as np


def LCSlength(x, y, m, n, b, c):
    for i in range(0, m):
        for j in range(0, n):
            if x[i] == y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = 1
            else:
                if c[i - 1][j] > c[i][j - 1]:
                    c[i][j] = c[i - 1][j]
                    b[i][j] = 2
                else:
                    c[i][j] = c[i][j - 1]
                    b[i][j] = 3


def LCS(x, b, i, j):
    if i == -1 or j == -1:
        # 因为前面使用的for是从0开始的，所以这里b[0]也用到了
        return
    if b[i][j] == 1:
        LCS(x, b, i - 1, j - 1)
        print(x[i], end="")
    if b[i][j] == 2:
        LCS(x, b, i - 1, j)
    if b[i][j] == 3:
        LCS(x, b, i, j - 1)


x = [1, 2, 3, 4, 5, 6, 7, 8]
m = len(x)
y = [2, 3, 4, 5, 6, 9, 9, 9]
n = len(y)
b = np.zeros((m, n), dtype=int)
c = np.zeros((m, n), dtype=int)
LCSlength(x, y, m, n, b, c)
# print(c)
print("最长子序列长度: ", c[m - 1][n - 1])
LCS(x, b, m - 1, n - 1)
